package problem_everyday;

public class D2025_08_12 {
    class Solution {
        private static final int mod_num = 1000_000_000 + 7;

        // 记忆化搜索
        private int dfs(int n, int[] pow_x, int[] num, int index){
            // num[0] = 1 代表初始终止条件
            if(num[n] >= 0) {
                return num[n];
            }
            int sum_num = 0;
            for(int i=index; i<n; i++){
                if(pow_x[i] <= n){
                    sum_num = (sum_num + dfs(n-pow_x[i], pow_x, num, i+1)) % mod_num;
                } else {
                    break;
                }
            }
            num[n] = sum_num;
            return sum_num;
        }

        public int numberOfWays(int n, int x) {
            // 提前构造 pow(num, x)
            int[] pow_x = new int [n];
            for(int i=0; i<n; i++){
                pow_x[i] = 1;
                for(int j=0; j<x; j++){
                    pow_x[i] = pow_x[i] * (i+1);
                    if(pow_x[i] > n) break;
                }
            }

            int[] num = new int[n+1];
            num[0] = 1;
            for(int i=1; i<n+1; i++) num[i] = -1;
            return dfs(n, pow_x, num, 0);
        }
    }

    public static void main(String[] args) {
        Solution solution = new D2025_08_12().new Solution();
        int n = 6;
        int x = 1;
        System.out.println(solution.numberOfWays(n, x));
    }
}
